package leetcode.hash;

public class Manacher {
    public static int manacher(String s) {
        if (s == null || s.length() == 0)
            return 0;
        char[] str = manacherString(s); // 1221->#1#2#2#1
        int[] pArr = new int[str.length];//回文半径数组
        int R = -1, C = -1, max = Integer.MAX_VALUE;//R是回文右边界再往右一个位置
        for (int i = 0; i < str.length; i++) {
            //得到不用扩展就已经知道的以i为中心的回文区域
            //大情况1：初始半径为1，需要往外暴力扩展b
            //小情况1：中心为i的回文直径长度，不需要扩展
            //小情况2：半径为R-i+1，不需要扩展
            //小情况3：中心为i的回文直径长度还需要扩展
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
            //从上述最小回文区域往外扩展
            //为了让代码简洁，以上所有情况都扩展(不需要扩展的两种情况，第一次扩展就失败)
            //实际上只有两种情况需要扩展
            while (i + pArr[i] < str.length && i - pArr[i] > -1) {
                if (str[i + pArr[i]] == str[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = i;
            }
            max = Math.max(max, pArr[i]);
        }
        return max - 1;//半径减一正好是原始s的回文字串长度
    }

    public static char[] manacherString(String s) {
        char[] charArr = s.toCharArray();
        char[] res = new char[s.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = i % 2 == 0 ? '#' : charArr[index++];
        }
        return res;
    }
}
